/**
 * @param {number[]} nums
 * @return {number}
 */
// 要求不修改原数组且空间复杂度为o(1)。（即不能对其排序）
// 混个通过（哈希表）
var findDuplicate1 = function (nums) {
  let m = new Map()
  for (let a of nums) {
    if (m.has(a)) {
      return a
    } else {
      m.set(a, 1)
    }
  }
}
// 两次遍历超时
var findDuplicate2 = function (nums) {
  for (let i = 1; i <= nums.length - 1; i++) {
    let n = 0
    for (let j = 0; j < nums.length; j++) {
      if (nums[j] == i) {
        n++
      }
    }
    if (n > 1) return i
  }
}
// 二分查找？查找个鸡毛
var findDuplicate3 = function (nums) {
}
console.log(findDuplicate3([1, 3, 4, 2, 2]))